package com.pocket.demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 搜索插入位置
 *  问题描述：
 *      以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 *  示例：
 *      输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 *      输出：[[1,6],[8,10],[15,18]]
 *      解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 *      输入：intervals = [[1,4],[4,5]]
 *      输出：[[1,5]]
 *
 *  思路：
 *
 *  应用：
 *      在做视频裁剪时，获取的数据源是N个片段，每个片段就是时间数组。对裁剪视频片段进行合并时，需要对视频片段进行排序、合并。
 *
 *  题目来源：
 *      https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
 */
public class __Array_Merge_Intervals {

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0){
            return new int[0][2];
        }

        // 对各区间左边界进行升序排列
        Arrays.sort(intervals, new Comparator<int[]>(){
            // 重写Comparator的compare方法,为负表示小于，为正表示大于
            public int compare(int[] interval1, int[] interval2){
                return interval1[0] - interval2[0];
            }
        });
        // 创建merged集合记录合并后的
        List<int[]> merged = new ArrayList<>();
        for(int i = 0; i < intervals.length; i++){
            // 记录左右边界
            int l = intervals[i][0], r = intervals[i][1];
            // 若集合为空或左边区间的右边界小于右边区间的左边界，则直接加上
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < l){
                merged.add(new int[]{l,r});
            } else{
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], r);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public static void main(String[] args) {
        System.out.println(merge(new int[][] {{1,3},{2,6},{8,10},{15,18}}));
        System.out.println(merge(new int[][] {{1,4},{4,5}}));
    }
}
